//反转单链表
#include<stdio.h>
#include<stdlib.h>


struct ListNode
{
	int val;
	struct ListNode* next;
};

void SLTNodePrintf(struct ListNode* ps)
{
	struct ListNode* cur = ps;
	while (cur)
	{
		printf("%d->", cur->val);
		cur = cur->next;
	}
	printf("NULL\n");
}


//struct ListNode* reverseList(struct ListNode* head)
//{
//	//头插法  1 2 3 4 头插完为4 3 2 1
//	struct ListNode* cur = head;
//	struct ListNode* CurNext = NULL;
//	struct ListNode* newhead = NULL;
//	while (cur)
//	{
//		//记录下一个结点 
//		CurNext = cur->next;
//
//		//头插
//		cur->next = newhead;
//		newhead = cur;
//		cur = CurNext;
//	}
//	return newhead;
//}
//

//方法二 三指针法
struct ListNode* reverseList(struct ListNode* head)
{
	struct ListNode* n1 = NULL;
	struct ListNode* n2 = head;
	struct ListNode* n3 = NULL;
	if (n2 != NULL)
	{
		n3 = n2->next;

	}
	while (n2)
	{
		n2->next = n1;

		n1 = n2;
		n2 = n3;
		if (n3 != NULL)
			n3 = n3->next;
	}
	return n1;
}

int main()
{
	struct ListNode* n1 = malloc(sizeof(struct ListNode));
	struct ListNode* n2 = malloc(sizeof(struct ListNode));
	struct ListNode* n3 = malloc(sizeof(struct ListNode));
	struct ListNode* n4 = malloc(sizeof(struct ListNode));

	n1->val = 1;
	n2->val = 2;
	n3->val = 3;
	n4->val = 4;

	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = NULL;
	SLTNodePrintf(n1);

	struct ListNode* newnode = reverseList(n1);
	SLTNodePrintf(newnode);

	return 0;
}